import common.ListNode;

/**
 * 234. Palindrome Linked List 回文链表
 * https://leetcode-cn.com/problems/palindrome-linked-list/
 */
class PalindromeLinkedList {
    /**
     * 方法：判断一个链表是否为回文链表。先找到链表中点，将后半部分反转，然后与前半部分比较。
     * 
     * Args:
     *   head: ListNode类型，输入链表的头节点
     * 
     * Returns:
     *   boolean类型，如果链表是回文链表返回true，否则返回false
     * 
     * Time: O(n)，其中n是链表的长度。需要遍历链表找到中点，反转后半部分，以及比较两半部分。
     * 
     * Space: O(1)，只使用了常数级别的额外空间
     */
    public boolean isPalindrome(ListNode head) {
        ListNode mid = middleNode(head);
        ListNode head2 = reverseList(mid);
        while (head2 != null){
            if(head.val != head2.val){
                return false;
            }
            head = head.next;
            head2 = head2.next;
        }
        return true;
    }
    // 876. 链表的中间结点
    private ListNode middleNode(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // 206. 反转链表
    private ListNode reverseList(ListNode head){
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}